package wwl.lsf.hellospringboot.test.算法;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class 最长字母 {

  public static void main(String[] args) {
    int i = lengthwwl("abba");
    System.out.println(i);
  }

  public static int lengthwwl(String s) {
    int result = 0, i = 0, length = s.length();
    Map<Character, Integer> map = new HashMap<>();
    for (int j = 0; j < length; j++) {
      if (map.containsKey(s.charAt(j))) {
        //精华所在,这个要取上次重复的最高位置,并不是当前字母的重复位置
        i = Math.max(map.get(s.charAt(j)), i);
      }
      //当前的位置减去上次重复的位置,就是长度,但是这个长度有可能没有历史的长度大,取大的
      result = Math.max(result, j - i + 1);
      //更新下角标位置
      map.put(s.charAt(j), j + 1);
    }
    return result;
  }

  public static int lengthOfLongestSubstringmap(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>(); // current index of character
    // try to extend the range [i, j]
    for (int j = 0, i = 0; j < n; j++) {
      if (map.containsKey(s.charAt(j))) {
        i = map.get(s.charAt(j));
//        i = Math.max(map.get(s.charAt(j)), i);
      }
      ans = Math.max(ans, j - i + 1);
      map.put(s.charAt(j), j + 1);
    }
    return ans;
  }


  public static int lengthOfLongestSubstringhuadong(String s) {
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int ans = 0, i = 0, j = 0;
    while (i < n && j < n) {
      // try to extend the range [i, j]
      if (!set.contains(s.charAt(j))) {
        set.add(s.charAt(j++));
        ans = Math.max(ans, j - i);
      } else {
        set.remove(s.charAt(i++));
      }
    }
    return ans;
  }

  public static int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j <= n; j++) {
        if (allUnique(s, i, j)) {
          ans = Math.max(ans, j - i);
        }
      }
    }
    return ans;
  }

  public static boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i < end; i++) {
      Character ch = s.charAt(i);
      if (set.contains(ch)) {
        return false;
      }
      set.add(ch);
    }
    return true;
  }

}
